package com.tlvip.arithmetic.ch07;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>description：归并排序</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/26/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class MergerSort {

    public static void main(String[] args) {
        int data[] = {9, 8, 7, 0, 1, 2, 5, 3};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    public static void mergeSort(int data[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(data, left, mid);
            mergeSort(data, mid + 1, right);
            //分完了，需要合并
            merge(data, left, mid, right);
        }
    }

    public static void merge(int data[], int left, int mid, int right) {
        int temp[] = new int[data.length];
        // 表示左边第一个数的位置
        int point1 = left;
        // 表示右边的第一个数的位置
        int point2 = mid + 1;
        // 表示我们当前已经到了哪个位置了
        int loc = left;
        while (point1 <= mid && point2 <= right) {
            if (data[point1] < data[point2]) {
                temp[loc] = data[point1];
                point1++;
                loc++;
            } else {
                temp[loc] = data[point2];
                point2++;
                loc++;
            }
        }
        // 接下来，移动元素
        while (point1 <= mid) {
            temp[loc++] = data[point1++];
        }
        while (point2 <= right) {
            temp[loc++] = data[point2++];
        }
        // 将排序结果从临时数组赋值到原数组中
        for (int i = left; i <= right; i++) {
            data[i] = temp[i];
        }
    }


//    /**
//     * 初始化数字序列
//     *
//     * @param size
//     * @return
//     */
//    public static int[] getData(int size) {
//        int data[] = new int[size];
//        Random random = new Random();
//        for (int i = 0; i < size; i++) {
//            data[i] = random.nextInt(1000);
//        }
//        return data;
//    }
}
